-- see 67.hs for a much better solution
type Triangle = [[Int]]
type Row = [Int]
type Coord = (Int,Int)

next triangle row col
    | row < length triangle = (left,right)
    | otherwise = error "end of triangle"
      where left = nextRow !! col
            right = nextRow !! (col+1)
            nextRow = triangle !! (row+1)

up :: Triangle -> Coord -> [Coord]
up triangle (row,col)
   | row == 0 = []
   | col == 0 = [(prevRow,0)]
   | col + 1 == (length $ triangle !! row) = [(prevRow, leftCol)]
   | otherwise = [(prevRow, leftCol),(prevRow, rightCol)]
     where prevRow = row -1
           leftCol = col -1
           rightCol = col

bestSumTo :: Triangle -> Coord -> Int
bestSumTo triangle (0,0) = triangle !! 0 !! 0
bestSumTo triangle coord@(row,col)
          | length ups == 1 = oneValue
          | oneValue > otherValue = oneValue
          | otherwise = otherValue
            where ups = up triangle coord
                  oneValue = curValue + bestSumTo triangle (ups !! 0)
                  otherValue = curValue + bestSumTo triangle (ups !! 1)
                  curValue = triangle !! row !! col


challenge :: Triangle
challenge = 
  [[3],
   [7,5],
   [2,4,6],
   [8,5,9,3]]

realChallenge :: Triangle
realChallenge =
 [[75],
  [95, 64],
  [17, 47, 82],
  [18, 35, 87, 10],
  [20, 04, 82, 47, 65],
  [19, 01, 23, 75, 03, 34],
  [88, 02, 77, 73, 07, 63, 67],
  [99, 65, 04, 28, 06, 16, 70, 92],
  [41, 41, 26, 56, 83, 40, 80, 70, 33],
  [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
  [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
  [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
  [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
  [63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
  [04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23]]

main = foldr max 0 (map (bestSumTo realChallenge) [(length realChallenge -1,col)| col <- [0.. length realChallenge - 1]])
              
       

